/*
 * @lc app=leetcode.cn id=909 lang=cpp
 * @lcpr version=30204
 *
 * [909] 蛇梯棋
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution {
public:
    int snakesAndLadders(vector<vector<int>>& board) {
        int n = board.size();
        int target = n * n;
        vector<bool> visited(target + 1, false); // 记录是否访问过
        queue<pair<int, int>> q; // 存储位置和步数
        q.push({1, 0});
        visited[1] = true;
        
        while (!q.empty()) {
            auto [pos, steps] = q.front();
            q.pop();
            
            // 尝试掷骰子的6种可能
            for (int i = 1; i <= 6; ++i) {
                int next_pos = pos + i;
                if (next_pos > target) break; // 超出棋盘范围
                
                // 将数字转换为坐标
                int row = n - 1 - (next_pos - 1) / n;
                int col = (next_pos - 1) % n;
                // 偶数行（从下往上数）需要反转列
                if ((n - 1 - row) % 2 == 1) {
                    col = n - 1 - col;
                }
                
                // 检查是否有蛇或梯子
                if (board[row][col] != -1) {
                    next_pos = board[row][col];
                }
                
                // 到达终点
                if (next_pos == target) {
                    return steps + 1;
                }
                
                // 未访问过则加入队列
                if (!visited[next_pos]) {
                    visited[next_pos] = true;
                    q.push({next_pos, steps + 1});
                }
            }
        }
        
        // 无法到达终点
        return -1;
    }
};
// @lc code=end



/*
// @lcpr case=start
// [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]\n
// @lcpr case=end

// @lcpr case=start
// [[-1,-1],[-1,3]]\n
// @lcpr case=end

 */

